/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
 * <p>
 * 提取单词 
 * s = "catsanddog", 
 * dict = ["cat", "cats", "and", "sand", "dog"].
 * A solution is ["cats and dog", "cat sand dog"].
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class WordBreakII {

    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<>();
        //用于记录已经做好分词的子串，加快速度
        Map<String,List<String>> memorized = new HashMap<>();
        result = tokenizerString(s, wordDict,memorized );
        return result;
    }
    
    /**记录已经做好分词的子串，加快速度
     * @param s
     * @param wordDict
     * @param memorized
     * @return
     * @author towan
     * 2015年6月14日
     */
    private List<String> tokenizerString(String s, Set<String> wordDict,
            Map<String, List<String>> memorized) {
        List<String> result = new ArrayList<>();
        if(s==null || s.length() == 0){
           return result; 
        }
        //从已保存的结果中找出提取后的单词，加快提取速度
        if(memorized.containsKey(s)){
            return memorized.get(s);
        }
        if(wordDict.contains(s)){
            result.add(s);//整个串是一个结果
        }
        int len = s.length();
        for(int i=0;i<len;i++){
            String prefix = s.substring(0, i);
            if(wordDict.contains(prefix)){
                //这个前缀是一个单词，递归调用函数
                for(String segSuffix:tokenizerString(s.substring(i, len), wordDict, memorized)){
                    if(segSuffix!=null){
                        //如果后面部分能够提取出单词，那么将其加入到结果中
                        result.add(prefix+" "+segSuffix);
                    }
                }
            }
        }
        memorized.put(s, result);
        return result;
    }

    @Test
    public  void test() {
        Set<String> wordDict = new HashSet<>();
        wordDict.add("cat");
        wordDict.add("cats");
        wordDict.add("and");
        wordDict.add("sand");
        wordDict.add("dog");
        String s = "catsanddog";
        List<String> wordBreak = wordBreak(s , wordDict);
        System.out.println(wordBreak);
    }
}
